A common problem in computational science is the need to represent the geometry of an object or the structure of data. One method for representing such objects is to use a polygonal mesh. A system and method that generates a large polygonal mesh is described in U.S. Pat. No. 4,710,876, assigned to the assignee of the present invention. Other techniques, such as automatic mesh generation or terrain mapping from satellite data are also capable of generating large polygonal meshes. For example, the complex, curved surface of a human tooth can be approximated by using many thousands of triangles (or other polygon types) joined along their common edges.
The ability to represent geometry is important for many reasons. In computer graphics, polygonal meshes are used in the lighting and shading operations to generate images. Polygonal meshes are used in numerical analysis to represent the boundary of solid objects. From these representations, equations can be developed to solve such complex problems as heat flow, structural response, or electromagnetic propagation. Another application is in geometric modeling, where polygonal meshes are often used to determine object mass, center of gravity, and moments of inertia.
In the past, polygonal meshes were typically comprised of hundreds to thousands of polygons, and computer hardware and software has been designed to process such volumes of information. However, recent advances in computational science have resulted in techniques that generate hundreds of thousands or even millions of polygons. Such large numbers, while capturing the geometry of the object very precisely, often overwhelm computer systems. For example, most graphics systems today are incapable of rendering a million polygons at a speed that is not detrimental to interactive computation.
The basic problem is that techniques that generate large polygonal meshes are extremely valuable and cannot be easily modified to produce fewer polygons. Hence a general technique for reducing, or decimating, a mesh composed of a large number of polygons to one containing fewer polygons is necessary. Furthermore, for the decimation process to be truly effective, it must preserve the topological and shape properties of the original polygonal mesh.